﻿//【进阶】35.哈希(2)
//【头文件包含】
//C++的主要头文件
#include<iostream>//c++的输入输出流
using namespace std;
#include<string>
#include<vector>
#include<list>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
//C的主要头文件
//#include<stdio.h>
//#include<stdlib.h>
//#include<assert.h>
//#include<string.h> 
#include"HashTable.h"





//【命名空间】

//【结构体声明】【类声明】
//【函数声明】
void Test1();void Test2();void Test3();


//【主函数】
int main()
{
	Test1();
	Test2();
	Test3();


	cout << "****主函数结束****" << endl;
	return 0;
}

//【函数定义】


/*测试用例*/void Test1()
{
	cout << "****测试用例开始****"<< endl;
	unordered_set<int> us;
	us.insert(4);
	us.insert(2);
	us.insert(1);
	us.insert(5);
	us.insert(6);
	unordered_set<int>::iterator it = us.begin();
	while (it != us.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;

	unordered_map<string, int> um;
	um.insert(make_pair("find", 1));
	um.insert(make_pair("my", 2));
	um.insert(make_pair("soul", 3));
	um.insert(make_pair("cool", 4));
	unordered_map<string, int>::iterator it2 = um.begin();
	while (it2 != um.end())
	{
		cout << it2->first << ":" << it2->second << " ";
		++it2;
	}
	cout << endl;
	cout << "****测试用例结束****" << endl << endl;
}

/*测试用例*/void Test2()
{
	cout << "****测试用例开始****" << endl;
	CLOSE_HASH::TestHashTable_Closed();
	OPEN_HASH::TestHashTable_Open();
	cout << "****测试用例结束****" << endl<<endl;
}

/*测试用例*/void Test3()
{
	cout << "****测试用例开始****" << endl;

	cout << "****测试用例结束****" << endl << endl;
}




//【笔记】
//【进阶】34.哈希
	// unordered_map   unordered_set  （无序的map和set/底层是哈希实现的）
		// 用法和map、set基本一致，但不支持排序，unordered只支持单向迭代器,构建对象可以增、删、查、不可改
	//map、set与unordered_map   unordered_set区别和联系
		// 1.都支持key、key/value搜索场景，且功能使用基本一样
		// 2.map、set底层使用红黑树实现，增删查时间复杂度O（log_2_N） 
		// 3.unordered底层使用哈希实现，增删查时间复杂度O（1）
		// 4.遍历前者有序，迭代器双向，后者无序，单向迭代器
	//海量数据下利用哈希查找效率更高
	//哈希的概念
		//哈希是一种映射的对应关系：在排序中提到的计数排序也是利用了一种映射关系
		// 映射
			// 1.直接定值法：映射只跟关键字直接或间接相关（是一种相对映射）
			// 2.除留余数法：取key%10的结果建立映射关系
		//插入元素
			// 根据待插入元素的关键码，计算出该元素的存储位置并按此位置进行存放
		//搜索元素
			// 对元素的关键码进行相同计算，得到元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功
		//哈希的这种映射关系也叫散列 
		//但是
			// 哈希表如果两个值计算出结果相同，会出现哈希冲突，需要用一些方法进行处理
		//解决冲突的方法
			// 闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，把key存放到冲突位置中的“下一个”空位置中去。
			//1. 线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。//插入时，找到不冲突位置插入，删除时，采用伪删除进行标记
			//如果哈希表越满越容易发生冲突，冲突越多，效率越低 
//【进阶】35.哈希(2)
	// 映射
			// 1.直接定值法
				// 映射值是线性排列的,同时直接定值法不会发生哈希碰撞的，因为每一个值都有唯一的映射
				// 但如果存入数据分布不均匀，那大量的映射位置不存有效数据会存在巨大的空间浪费
			// 2.除留余数法：
				// 在限定大小空间中将值进行映射 index=key%m m=capacity()
				// 但会存在不同值映射值相同，发生哈希冲突，冲突越多效率越低
	//解决冲突的方法
			//1.闭散列--开放定制法（当前位置冲突，找空位置）(不能满了再增容，需要判断负载因子，负载因子和效率负相关)
				// 线性探测:依次向后找空位；负载因子控制在0.7
				// 二次探测:按i^2向后找 index_i=(index_0+i^2)/m；负载因子控制在0.5
				// 闭散列不能完全解决冲突问题，更好的办法还是开散列-哈希桶
			//2.开散列--拉链法（哈希桶）（冲突元素在统一映射下链接存储起来）
				// 已链表的形式将冲突的元素链接在对应映射位置下
				// 虽然开散列可以较好解决负载冲突，但随着冲突元素增多，效率也会降低
				// 因此开散列把负载因子控制到1，满负载也需要增容

		









